//一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 
//
// 
//
// 示例 1： 
//
// 输入：nums = [4,1,4,6]
//输出：[1,6] 或 [6,1]
// 
//
// 示例 2： 
//
// 输入：nums = [1,2,10,4,1,4,3,3]
//输出：[2,10] 或 [10,2] 
//
// 
//
// 限制： 
//
// 
// 2 <= nums.length <= 10000 
// 
//
// 
// Related Topics 位运算 数组 
// 👍 449 👎 0


package leetcode.editor.cn1;

//Java：数组中数字出现的次数

/**
 * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 * 输入：nums = [4,1,4,6]
 * 输出：[1,6] 或 [6,1]
 */
public class ShuZuZhongShuZiChuXianDeCiShuLcof {
    public static void main(String[] args) {
        Solution solution = new ShuZuZhongShuZiChuXianDeCiShuLcof().new Solution();
        // TO TEST
        int[] res = solution.singleNumbers(new int[]{1,2,10,4,1,4,3,3});
        for (int re : res) {
            System.out.println(re);
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] singleNumbers(int[] nums) {
            // 先计算两个数字的异或值
            int res = 0;
            for (int num : nums) {
                res = res ^ num;
            }

            // 找出res中最右边的一位，只有相等的才为1
            int div = 1;
            while ((div & res) == 0) {
                div = div << 1;
            }

            // 根据1的那位对原数组进行分组，如果与后为0，就表示a分组，与后为1，表示b分组
            int a = 0, b = 0;
            for (int num : nums) {
                if ((div & num) != 0) {
                    a = a ^ num;
                } else {
                    b = b ^ num;
                }
            }
            return new int[] {a, b};
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
